# -*- coding: utf-8 -*-

"""给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1:
输入: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出: 6
解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:
输入: grid = [[0,0,0,0,0,0,0,0]]
输出: 0

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1"""


class Solution:
    """一开始用动态规划：因为想到到每个岛能连接的最大岛屿是一定的，每递进一个位置，都与左侧上侧结果值有逻辑关系，用动态规划，几经测试，都有新出来的案例，暂时还没有找到完整的逻辑。
    那就暂时放弃动态规划的方法，用前面求最大矩形的类似思路，边遍历，边连接岛，用一个哈希字典记录，某个连接的岛屿开始小岛，以及当前岛屿的计数。
    同时也用以一个同样规模的矩阵来记录每个小岛所属的岛屿，利用题目给定的上下左右连接关系来合并岛屿，
    就可以利用动态规划来解决，因为一个岛初始所属岛屿是不会变的，这时候的关键就是建立初始岛到合并岛的映射，每遍历到一个位置，检查其左侧，上侧的实际岛屿再做操作
    
    island = {(0,0):1<实际岛>, (3,5):2<实际岛>, (7,8):(4,2)<引用岛>}
    dp[i][j] = island.key:=(3,5), 初始所属岛屿"""
    def maxAreaOfIsland(self, grid) -> int:
        hi, hj = len(grid)+1, len(grid[0])+1
        dp = [[None for _ in range(hj)] for _ in range(hi)]
        for row in grid:
            row.insert(0, 0)
        grid.insert(0, [0 for _ in range(hj)])

        answer = {}
        for i in range(1, hi):
            for j in range(1, hj):
                if grid[i][j]:
                    # 取出初始岛屿
                    dp_up, dp_left = dp[i-1][j], dp[i][j-1]
                    
                    # 追溯到各自实际岛屿
                    real_up = dp_up
                    if real_up:
                        count = answer[real_up]
                        while isinstance(count, tuple) and count in answer:
                            real_up = count
                            count = answer[real_up]
                    real_left = dp_left
                    if real_left:
                        count = answer[real_left]
                        while isinstance(count,tuple) and count in answer:
                            real_left = count
                            count = answer[real_left]

                    if real_up and real_left:
                        # 如果上侧左侧都有实际岛屿
                        if real_up != real_left:
                            # 上侧左侧都有岛屿，且实际岛屿不同，将上侧岛屿合并岛左侧，计数挪动+引用关联
                            answer[real_left] += answer[real_up]
                            answer[real_up] = real_left
                        # 连接到包围的岛屿
                        answer[real_left] += 1
                        dp[i][j] = real_left
                    elif real_up:
                        # 连接到上侧岛屿
                        answer[real_up] += 1
                        dp[i][j] = real_up
                    elif real_left:
                        # 连接到左侧岛屿
                        answer[real_left] += 1
                        dp[i][j] = real_left
                    else:
                        # 新建岛屿
                        dp[i][j] = (i, j)
                        answer[dp[i][j]] = 1
        max_area = 0
        for arae in answer.values():
            if isinstance(arae, int):
                max_area = max(max_area, arae)

        return max_area

if __name__ == '__main__':
    so = Solution()
    print(so.maxAreaOfIsland([[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]))
    print(so.maxAreaOfIsland([[0,0,0,0,0,0,0,0]]))
    print(so.maxAreaOfIsland([[1,1],[1,0]]))
    print(so.maxAreaOfIsland([[1,1,1],[1,0,1]]))
    print(so.maxAreaOfIsland([[0,1,1],[1,1,1]]))
    print(so.maxAreaOfIsland([[1,0,0,0,1,1,1,1,0,1,0,0,1,1,1,0,0,0,1,0,1,0,0,1,1,1,0],[1,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1],[1,0,1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,1,0,0,1,1,0,1,1,0,0],[0,0,0,1,1,1,0,0,0,1,1,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,0],[1,0,0,0,1,1,0,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,1],[0,0,1,1,1,1,0,1,1,0,1,0,0,0,1,1,0,0,0,1,1,0,1,1,0,1,1]]))
